package LEETCODE2023.BISHUA100;

import java.util.Arrays;

public class SolutionBM72 {

    public int FindGreatestSumOfSubArray1(int[] array) {
        int[] dp = new int[array.length];
        dp[0] = array[0];
        int ans=dp[0];
        for (int i = 1; i < array.length; i++) {
            dp[i] = Math.max(array[i], dp[i - 1] + array[i]);
            ans = Math.max(dp[i], ans);
        }
        return ans;
    }

    /**
     * wrong
     */
    public int FindGreatestSumOfSubArray(int[] array) {
        int max = 0;
        int ans = max;
        for (int i = 0; i < array.length; i++) {
            if (max + array[i] < 0) {
                max = 0;
            } else {
                max += array[i];
            }
            ans = Math.max(max, ans);
        }
        return ans;
    }
}
